﻿using System;
using System.Threading;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using ParallelRuntimeLibrary.Internal;

namespace ParallelRuntimeLibrary.Collections
{
    public class SegmentQueue<T>
    {
        private Segment mHead;
        private Segment mTail;
        private const int SegmentSize = 128;
        private const int SegmentSizeL1 = SegmentSize - 1;

        public SegmentQueue()
        {
            this.mHead = this.mTail = new Segment();
        }

        public SegmentQueue(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            this.InitializeFromCollection(collection);
        }

        private void InitializeFromCollection(IEnumerable<T> collection)
        {
            this.mHead = this.mTail = new Segment();
            int num = 0;

            foreach (T local in collection)
            {
                if (num >= SegmentSize)
                {
                    this.mTail = this.mTail.UnsafeGrow();
                    num = 0;
                }

                this.mTail.UnsafeAdd(local);
                num++;
            }
        }

        private void GetHeadTailPositions(out Segment head, out Segment tail, out int headLow, out int tailHigh)
        {
            head = this.mHead;
            tail = this.mTail;
            headLow = head.Low;
            tailHigh = tail.High;

            while (((head != this.mHead) || (tail != this.mTail)) || ((headLow != head.Low) || (tailHigh != tail.High)))
            {
                NativeMethod.SwitchToThread();
                head = this.mHead;
                tail = this.mTail;
                headLow = head.Low;
                tailHigh = tail.High;
            }
        }

        private List<T> ToList()
        {
            Segment segment;
            Segment segment2;
            int num;
            int num2;

            this.GetHeadTailPositions(out segment, out segment2, out num, out num2);

            if (segment == segment2)
                return segment.ToList(num, num2);

            List<T> list = new List<T>(segment.ToList(num, SegmentSizeL1));
            for (Segment segment3 = segment.Next; segment3 != segment2; segment3 = segment3.Next)
                list.AddRange(segment3.ToList(0, 0x1f));

            list.AddRange(segment2.ToList(0, num2));
            return list;
        }

        public void Enqueue(T item)
        {

            while (true)
            {
                if (this.mTail.TryAppend(item, ref this.mTail))
                    return;
                else
                {
                    if (this.mTail.TryAppend(item, ref this.mTail))
                        return;
                    else
                        NativeMethod.SwitchToThread();
                }
            }
        }

        public bool Dequeue(out T result)
        {
            while (true)
            {

                if (!(mHead.Low > mHead.High))
                {
                    if (this.mHead.TryRemove(out result, ref this.mHead))
                        return true;
                }
                else
                {
                    result = default(T);
                    return false;
                }
            }
        }

        public bool TryPeek(out T result)
        {
            while (true)
            {
                if (!this.mHead.IsEmpty)
                {
                    if (this.mHead.TryPeek(out result))
                        return true;
                }
                else
                {
                    result = default(T);
                    return false;
                }
            }
        }

        public bool IsEmpty
        {
            get
            {
                Segment head = this.mHead;
                if (head.IsEmpty)
                {
                    if (head.Next == null)
                        return true;

                    NativeMethod.SwitchToThread();

                    while (head.IsEmpty)
                    {
                        if (head.Next == null)
                            return true;

                        head = this.mHead;
                    }
                }
                return false;
            }
        }

        public int Count
        {
            get
            {
                Segment segment;
                Segment segment2;
                int num;
                int num2;

                this.GetHeadTailPositions(out segment, out segment2, out num, out num2);

                if (segment == segment2)
                    return ((num2 - num) + 1);

                int num3 = SegmentSize - num;
                for (Segment segment3 = segment.Next; segment3 != segment2; segment3 = segment3.Next)
                    num3 += SegmentSize;

                return num3 + (num2 + 1);
            }
        }



        private class Segment
        {

            internal T[] mArray;
            private int mHigh;
            private int mLow;
            private SegmentQueue<T>.Segment mNext;
            private bool[] mState;

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal int High
            {
                get
                {
                    return Math.Min(this.mHigh, 0x1f);
                }
            }

            internal bool IsEmpty
            {
                get
                {
                    return (this.Low > this.High);
                }
            }

            internal int Low
            {
                get
                {
                    return Math.Min(this.mLow, 0x20);
                }
            }

            internal SegmentQueue<T>.Segment Next
            {
                get
                {
                    return this.mNext;
                }
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal Segment()
            {
                this.mArray = new T[SegmentSize];
                this.mState = new bool[SegmentSize];
                this.mNext = null;
                this.mLow = 0;
                this.mHigh = -1;
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal bool TryAppend(T value, ref SegmentQueue<T>.Segment tail)
            {
                if (this.mHigh < SegmentSizeL1)
                {
                    int index = SegmentSize;

                    index = Interlocked.Increment(ref this.mHigh);
                    if (index <= 0x1f)
                    {
                        this.mArray[index] = value;
                        this.mState[index] = true;
                    }

                    if (index < SegmentSizeL1)
                        return true;

                    if (index == SegmentSizeL1)
                    {
                        this.Grow(ref tail);
                        return true;
                    }
                }
                return false;
            }

            internal bool TryPeek(out T result)
            {
                result = default(T);
                int low = this.Low;
                if (low > this.High)
                {
                    return false;
                }

                result = this.mArray[low];
                return true;
            }

            internal bool TryRemove(out T result, ref SegmentQueue<T>.Segment head)
            {
                int low = this.Low;

                for (int i = this.High; low <= i; i = this.High)
                {
                    if (Interlocked.CompareExchange(ref this.mLow, low + 1, low) == low)
                    {

                        while (this.mState[low] == false)
                        { } // NativeMethod.SwitchToThread();


                        result = this.mArray[low];

                        if ((low + 1) >= SegmentSize)
                        {
                            while (this.mNext == null)
                            { } //NativeMethod.SwitchToThread();

                            head = this.mNext;
                        }

                        return true;
                    }
                    NativeMethod.SwitchToThread();

                    low = this.Low;
                }

                result = default(T);
                return false;
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal void UnsafeAdd(T value)
            {
                this.mHigh++;
                this.mArray[this.mHigh] = value;
                this.mState[this.mHigh] = true;
            }

            internal SegmentQueue<T>.Segment UnsafeGrow()
            {
                SegmentQueue<T>.Segment segment = new SegmentQueue<T>.Segment();
                this.mNext = segment;
                return segment;
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal void Grow(ref SegmentQueue<T>.Segment tail)
            {
                this.mNext = new SegmentQueue<T>.Segment();
                tail = this.mNext;
            }

            internal List<T> ToList(int start, int end)
            {
                List<T> list = new List<T>();
                for (int i = start; i <= end; i++)
                {
                    while (this.mState[i] == null)
                        NativeMethod.SwitchToThread();

                    list.Add(this.mArray[i]);
                }
                return list;
            }

            
        }

    }
}
